package structures.search;

public class InsertValueSearch {

    private static final int[] dataArray1 =
        {2, 3, 3, 6, 6, 6, 7, 9, 9, 9, 10, 10, 13, 15, 15, 16, 16, 18, 19, 19};
    private static final int[] dataArray2 =
            {0, 1, 1, 2, 6, 6, 6, 8, 10, 10, 11, 13, 14, 14, 15, 15, 15, 17, 17};

    private static final int VALUE = 20;

    public static void main(String[] args) {
        // 查找数据
        int index = insertValueSearch(dataArray1, VALUE, 0, dataArray1.length - 1);
        if (index != -1) {
            System.out.println("---- 找到数据索引值： " + index + " ----");
        } else {
            System.out.println("---- 未找到数据 ----");
        }

    }

    private static int insertValueSearch(int[] dataArray, int targetValue, int start, int end) {
        if (start > end || targetValue < dataArray[start] ||
            targetValue > dataArray[end]) {
            return -1;
        }

        int mid = start + (end - start) *
                (targetValue - dataArray[start]) /
                (dataArray[end] - dataArray[start]);
        int midValue = dataArray[mid];
        if (targetValue > midValue) {
            return insertValueSearch(dataArray, targetValue, mid + 1, end);
        }

        if (targetValue == midValue) {
            return mid;
        }

        return insertValueSearch(dataArray, targetValue, start, mid);
    }
}
